package string.leetcode.easy;

/**
 * @author bruin_du
 * @description 打印从1到最大的n位数
 * @date 2022/7/27 14:52
 **/
public class Offer17_PrintNumbers {
    int nine = 0, start, n, count = 0;
    char[] arr;
    char[] num = new char[]{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    int[] res;
    public int[] printNumbers(int n) {
        this.n = n;
        arr = new char[n];
        start = n - 1;
        res = new int[(int) Math.pow(10, n) - 1];
        recursion(0);
        return res;
    }

    void recursion(int x) {
        if (x == n) {
            String str = String.valueOf(arr).substring(start);
            if (!"0".equals(str)) {
                res[count++] = Integer.parseInt(str);
            }
            if (n - start == nine) {
                start--;
            }
            return;
        }
        for (char ch : num) {
            if (ch == '9') nine++;
            arr[x] = ch;
            recursion(x + 1);
        }
        nine--;
    }
}
